package leetcode;

import java.util.Arrays;

/**
 * @description:
 * 给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
 * 说明:
 * 初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
 * 你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
 * 示例:
 * 输入:
 * nums1 = [1,2,3,0,0,0], m = 3
 * nums2 = [2,5,6], n = 3
 * 输出: [1,2,2,3,5,6]
 *
 * 实现思路：
 * 因原数组都是有序数组，只需要从两个数组的最后一个元素开始对比，寻找最大值赋值给最终数组。
 *
 *     如果数组二元素耗尽，则得到最终数组。
 *     如果数组一元素耗尽，则需要将原数组二剩余元素赋值给最终数组。
 * @author: walt-zhong
 * @createDate: 2021/3/10
 */
public class MergeTwoArray {

    public static void  main(String []args){
        int [] arr1 = {1,2,3,4,0,0,0};
        int [] arr2 = {4,7,9};
      //  merge(arr1,3,arr2,3);
        merge2(arr1,4,arr2,3);
        System.out.println("result"+ Arrays.toString(arr1));
    }

    public static void merge(int[] nums1,int m,int []nums2,int n){

        if(m==0){
            System.arraycopy(nums2,0,nums1,0,n);
        }

        int i1 = m-1;
        int i2 = n-1;
        while (i2>=0){
            if(i1<0){//nums1中的元素已经全部遍历完，将nums2中的全部复制过来即可
                System.arraycopy(nums2,0,nums1,0,i2+1);
                break;
            }
            if(nums1[i1] >= nums2[i2]){
                nums1[i1+i2+1] = nums1[i1--];
            }else{
                nums1[i1+i2+1] = nums2[i2--];
            }
        }
    }

    public static void merge2(int [] nums1, int m,int []nums2,int n){
        int k = m + n;
        for(int index = k-1,nums1Index = m-1,nums2Index = n-1;index >=0;index --){
            if(nums1Index < 0){
                nums1[index] = nums2[nums2Index--];
            }else if(nums2Index < 0){
                break;
            }else if(nums1[nums1Index] >= nums2[nums2Index]){
                nums1[index] = nums1[nums1Index--];
            }else{
                nums1[index] = nums2[nums2Index--];
            }
        }
    }
}
